home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / rows.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  5.6 KB  |  306 lines  |  [TEXT/R*ch]
  1. #include "port.h"
  2. #include "sparse_int.h"
  3.  
  4.  
  5. /*
  6.  *  allocate a new row vector 
  7.  */
  8. sm_row *
  9. sm_row_alloc()
  10. {
  11.     register sm_row *prow;
  12.  
  13. #ifdef FAST_AND_LOOSE
  14.     if (sm_row_freelist == NIL(sm_row)) {
  15.     prow = ALLOC(sm_row, 1);
  16.     } else {
  17.     prow = sm_row_freelist;
  18.     sm_row_freelist = prow->next_row;
  19.     }
  20. #else
  21.     prow = ALLOC(sm_row, 1);
  22. #endif
  23.  
  24.     prow->row_num = 0;
  25.     prow->length = 0;
  26.     prow->first_col = prow->last_col = NIL(sm_element);
  27.     prow->next_row = prow->prev_row = NIL(sm_row);
  28.     prow->flag = 0;
  29.     prow->user_word = NIL(char);        /* for our user ... */
  30.     return prow;
  31. }
  32.  
  33.  
  34. /*
  35.  *  free a row vector -- for FAST_AND_LOOSE, this is real cheap for rows;
  36.  *  however, freeing a column must still walk down the column discarding
  37.  *  the elements one-by-one; that is the only use for the extra '-DCOLS'
  38.  *  compile flag ...
  39.  */
  40. void
  41. sm_row_free(prow)
  42. register sm_row *prow;
  43. {
  44. #if defined(FAST_AND_LOOSE) && ! defined(COLS)
  45.     if (prow->first_col != NIL(sm_element)) {
  46.     /* Add the linked list of row items to the free list */
  47.     prow->last_col->next_col = sm_element_freelist;
  48.     sm_element_freelist = prow->first_col;
  49.     }
  50.  
  51.     /* Add the row to the free list of rows */
  52.     prow->next_row = sm_row_freelist;
  53.     sm_row_freelist = prow;
  54. #else
  55.     register sm_element *p, *pnext;
  56.  
  57.     for(p = prow->first_col; p != 0; p = pnext) {
  58.     pnext = p->next_col;
  59.     sm_element_free(p);
  60.     }
  61.     FREE(prow);
  62. #endif
  63. }
  64.  
  65.  
  66. /*
  67.  *  duplicate an existing row
  68.  */
  69. sm_row *
  70. sm_row_dup(prow)
  71. register sm_row *prow;
  72. {
  73.     register sm_row *pnew;
  74.     register sm_element *p;
  75.  
  76.     pnew = sm_row_alloc();
  77.     for(p = prow->first_col; p != 0; p = p->next_col) {
  78.     (void) sm_row_insert(pnew, p->col_num);
  79.     }
  80.     return pnew;
  81. }
  82.  
  83.  
  84. /*
  85.  *  insert an element into a row vector 
  86.  */
  87. sm_element *
  88. sm_row_insert(prow, col)
  89. register sm_row *prow;
  90. register int col;
  91. {
  92.     register sm_element *test, *element;
  93.  
  94.     /* get a new item, save its address */
  95.     sm_element_alloc(element);
  96.     test = element;
  97.     sorted_insert(sm_element, prow->first_col, prow->last_col, prow->length, 
  98.             next_col, prev_col, col_num, col, test);
  99.  
  100.     /* if item was not used, free it */
  101.     if (element != test) {
  102.     sm_element_free(element);
  103.     }
  104.  
  105.     /* either way, return the current new value */
  106.     return test;
  107. }
  108.  
  109.  
  110. /*
  111.  *  remove an element from a row vector 
  112.  */
  113. void
  114. sm_row_remove(prow, col)
  115. register sm_row *prow;
  116. register int col;
  117. {
  118.     register sm_element *p;
  119.  
  120.     for(p = prow->first_col; p != 0 && p->col_num < col; p = p->next_col)
  121.     ;
  122.     if (p != 0 && p->col_num == col) {
  123.     dll_unlink(p, prow->first_col, prow->last_col, 
  124.                 next_col, prev_col, prow->length);
  125.     sm_element_free(p);
  126.     }
  127. }
  128.  
  129.  
  130. /*
  131.  *  find an element (if it is in the row vector)
  132.  */
  133. sm_element *
  134. sm_row_find(prow, col)
  135. sm_row *prow;
  136. int col;
  137. {
  138.     register sm_element *p;
  139.  
  140.     for(p = prow->first_col; p != 0 && p->col_num < col; p = p->next_col)
  141.     ;
  142.     if (p != 0 && p->col_num == col) {
  143.     return p;
  144.     } else {
  145.     return NIL(sm_element);
  146.     }
  147. }
  148.  
  149. /*
  150.  *  return 1 if row p2 contains row p1; 0 otherwise
  151.  */
  152. int 
  153. sm_row_contains(p1, p2)
  154. sm_row *p1, *p2;
  155. {
  156.     register sm_element *q1, *q2;
  157.  
  158.     q1 = p1->first_col;
  159.     q2 = p2->first_col;
  160.     while (q1 != 0) {
  161.     if (q2 == 0 || q1->col_num < q2->col_num) {
  162.         return 0;
  163.     } else if (q1->col_num == q2->col_num) {
  164.         q1 = q1->next_col;
  165.         q2 = q2->next_col;
  166.     } else {
  167.         q2 = q2->next_col;
  168.     }
  169.     }
  170.     return 1;
  171. }
  172.  
  173.  
  174. /*
  175.  *  return 1 if row p1 and row p2 share an element in common
  176.  */
  177. int 
  178. sm_row_intersects(p1, p2)
  179. sm_row *p1, *p2;
  180. {
  181.     register sm_element *q1, *q2;
  182.  
  183.     q1 = p1->first_col;
  184.     q2 = p2->first_col;
  185.     if (q1 == 0 || q2 == 0) return 0;
  186.     for(;;) {
  187.     if (q1->col_num < q2->col_num) {
  188.         if ((q1 = q1->next_col) == 0) {
  189.         return 0;
  190.         }
  191.     } else if (q1->col_num > q2->col_num) {
  192.         if ((q2 = q2->next_col) == 0) {
  193.         return 0;
  194.         }
  195.     } else {
  196.         return 1;
  197.     }
  198.     }
  199. }
  200.  
  201.  
  202. /*
  203.  *  compare two rows, lexical ordering
  204.  */
  205. int 
  206. sm_row_compare(p1, p2)
  207. sm_row *p1, *p2;
  208. {
  209.     register sm_element *q1, *q2;
  210.  
  211.     q1 = p1->first_col;
  212.     q2 = p2->first_col;
  213.     while(q1 != 0 && q2 != 0) {
  214.     if (q1->col_num != q2->col_num) {
  215.         return q1->col_num - q2->col_num;
  216.     }
  217.     q1 = q1->next_col;
  218.     q2 = q2->next_col;
  219.     }
  220.  
  221.     if (q1 != 0) {
  222.     return 1;
  223.     } else if (q2 != 0) {
  224.     return -1;
  225.     } else {
  226.     return 0;
  227.     }
  228. }
  229.  
  230.  
  231. /*
  232.  *  return the intersection
  233.  */
  234. sm_row *
  235. sm_row_and(p1, p2)
  236. sm_row *p1, *p2;
  237. {
  238.     register sm_element *q1, *q2;
  239.     register sm_row *result;
  240.  
  241.     result = sm_row_alloc();
  242.     q1 = p1->first_col;
  243.     q2 = p2->first_col;
  244.     if (q1 == 0 || q2 == 0) return result;
  245.     for(;;) {
  246.     if (q1->col_num < q2->col_num) {
  247.         if ((q1 = q1->next_col) == 0) {
  248.         return result;
  249.         }
  250.     } else if (q1->col_num > q2->col_num) {
  251.         if ((q2 = q2->next_col) == 0) {
  252.         return result;
  253.         }
  254.     } else {
  255.         (void) sm_row_insert(result, q1->col_num);
  256.         if ((q1 = q1->next_col) == 0) {
  257.         return result;
  258.         }
  259.         if ((q2 = q2->next_col) == 0) {
  260.         return result;
  261.         }
  262.     }
  263.     }
  264. }
  265.  
  266. int 
  267. sm_row_hash(prow, modulus)
  268. sm_row *prow;
  269. int modulus;
  270. {
  271.     register int sum;
  272.     register sm_element *p;
  273.  
  274.     sum = 0;
  275.     for(p = prow->first_col; p != 0; p = p->next_col) {
  276.     sum = (sum*17 + p->col_num) % modulus;
  277.     }
  278.     return sum;
  279. }
  280.  
  281. /*
  282.  *  remove an element from a row vector (given a pointer to the element) 
  283.  */
  284. void
  285. sm_row_remove_element(prow, p)
  286. register sm_row *prow;
  287. register sm_element *p;
  288. {
  289.     dll_unlink(p, prow->first_col, prow->last_col, 
  290.             next_col, prev_col, prow->length);
  291.     sm_element_free(p);
  292. }
  293.  
  294.  
  295. void
  296. sm_row_print(fp, prow)
  297. FILE *fp;
  298. sm_row *prow;
  299. {
  300.     sm_element *p;
  301.  
  302.     for(p = prow->first_col; p != 0; p = p->next_col) {
  303.     (void) fprintf(fp, " %d", p->col_num);
  304.     }
  305. }
  306.